Most modern communication systems transmit data over time-varying, dispersive communication channels. Among the distortions introduced by the channel, inter-symbol interference (ISI) is significant because it severely degrades the performance of the receiver. To mitigate the effects of ISI, many receivers use equalizers. The general architecture of an equalizer comprises filters, adders for combining the output of the filters, and decision devices. The filters are linear finite-impulse-response (FIR) with complex coefficients. A decision device operates on complex inputs and outputs complex values that are representative of the signal constellation points of the modulation scheme.
In general, the equalizer filter coefficients are jointly optimized according to a criterion suitable for the communication system. Determining the optimal equalizer filter coefficients is a computationally intensive task because it requires the solution to a large set of linear equations. Two general approaches are commonly used today: the first approach is the adaptive approach, and the second is the direct matrix inversion approach.
In the adaptive approach, the equalizer filter coefficients are first set to some initial values. The output error signal, defined as the difference between the input and the output of the equalizer decision device, is then used to recursively adjust the equalizer filter coefficients toward the optimal settings. Depending on the coefficient adaptation algorithm employed, a training sequence may be required. A training sequence is a known set of symbols that the transmitter sends along with the data. In U.S. Pat. No. 5,068,873 issued to Murakami, the least mean square (LMS) or Kalman filter algorithm is used for adaptation. A training sequence is required for that approach. The LMS algorithm requires O(M) complex operations per iteration, where M is the total number of coefficients to optimize. Furthermore, a large number of iterations (&gt;&gt;M) is required for the equalizer filter coefficients to converge to the optimal values. While Kalman filter algorithm converges faster to the optimal solution, it requires O(M.sup.2) operations per iteration. Similarly, U.S. Pat. No. 5,283,811 issued to Chennankeshu, et al. employs the fast Kalman algorithm for decision-feedback equalizer (DFE) coefficient adaptation. U.S. Pat. No. 3,974,449 issued to Falconer describes a DFE adaptation method that does not use training sequences.
In the direct matrix inversion approach, a response of the channel to the signaling pulse is first estimated. This estimate is the response, filtered by the receiver filter, of the channel to the transmitter spectral-shaping pulse. The equalizer coefficients are then obtained from the estimate of the response of the channel to the signaling pulse by solving a set of complex-valued linear equations. In general, the solution of these equations requires the inversion of an M.times.M square matrix, which requires O(M.sup.3) complex multiplications. U.S. Pat. No. 5,436,929 issued to Kawas Kaleh utilizes positive-definite and Hermitian symmetric properties of the square matrix so that a Cholesky decomposition can be used. The Cholesky decomposition requires O(M.sup.3) complex multiplications to factor a positive-definite, Hermitian symmetric matrix into the product of lower and upper triangular matrices. The upper triangular matrix is equal to the Hermitian transpose of the lower triangular matrix. The triangular matrices are easily invertible, requiring O(M.sup.2) multiplications. U.S. Pat. No. 5,790,598 issued to Moreland, et al. describes a recursive method using the Cholesky decomposition. Both of these techniques still require O(M.sup.3) complex multiplications. Finally, Al-Dhahir and Cioffi developed an optimization method for the DFE using a fast Cholesky decomposition. The algorithm requires approximately O(N.sub.f N.sub.b) complex multiplications, where N.sub.f and N.sub.b are, respectively, the number of feedforward filter (FFF) and feedback filter (FBF) coefficients. This method, however, can only be used under the following restrictions:
1) The discrete-time noise at the input of the DFE is white; PA1 2) The number of feedback filter coefficients is equal to the number of taps in the estimated response of the channel; and PA1 3) The decision delay of the DFE is equal to N.sub.f -1.
If these assumptions are violated, the coefficients obtained by this method are significantly sub-optimal, and the performance of the DFE is greatly degraded.
It can therefore be seen that in general, the optimization of the equalizer coefficients require at least O(M.sup.3) complex multiplies if direct matrix inversion is used. The complexity is even higher for the adaptive approach due to the large number of iterations required. Although a lower complexity O(N.sub.f N.sub.b) approach exists, it is applicable only under certain restrictions. Thus there is a need for efficient method and apparatus for computing the equalizer filter coefficients without any restrictions.